package LeetCode;

public class LC_400_NthDigit {

    public static void main(String[] args) {

    }

    static class Solution {
        public int findNthDigit(int n) {
            int k = 1;
            long len = 0;
            while (n > len) {
                len += (int) (9 * k * Math.pow(10, k - 1));
                k++;
            }
            k--;
            len -= (int) (9 * k * Math.pow(10, k - 1));
            int num;
            if ((n - len) % k == 0) {
                num = (int) ((int) Math.pow(10, k - 1) + (n - len) / k - 1);
                String s = String.valueOf(num);
                return Integer.parseInt("" + s.charAt(s.length() - 1));
            } else {
                num = (int) ((int) Math.pow(10, k - 1) + (n - len) / k);
                String s = String.valueOf(num);
                return Integer.parseInt("" + s.charAt((int) ((n - len) % k - 1)));
            }
        }

    }

    static class Solution_2 {
        public int findNthDigit(int m) {
            long n = m;
            long start = 1, len = 1, count = 9;
            while (n > len * count) {
                n = n - len * count;
                len++;
                count = count * 10;
                start = start * 10;
            }
            start = start + (n - 1) / len;
            return String.valueOf(start).charAt((int) ((n - 1) % len)) - '0';
        }

    }
}